package Sequence;

public class Test0037 {
}

class Solution0037_1 {
    short[] columnRecords = new short[9];
    short[] rowRecords = new short[9];
    short[] blockRecords= new short[9];

    public void solveSudoku(char[][] board) {
        init(board);
        backtrack(board,0,0);
    }


    public boolean backtrack(char[][] board, int row, int col) {

        if (board[row][col] != '.') {
            return next(board, row, col);
        }

        int block = getBlockIndex(row, col);
        for (int i = 1; i <= 9; i++){
            if(checkSudoku(i,row,col, block)){
                setSudoku(i,row,col,block);
                board[row][col] = (char) ('0'+i);
                if (next(board,row,col)) return true;
                deleteSudoku(i,row,col,block);
                board[row][col] = '.';
            }
        }

        return false;
    }

    public boolean next(char[][] board, int row, int col) {
        if (col==8){
            if (row==8)return true;
            return backtrack(board,row+1,0);
        }

        return backtrack(board,row,col+1);
    }

    public void init(char[][] board) {
        for (int i = 0; i < 9; i++) {
            char[] chars = board[i];
            for (int j = 0; j < 9; j++) {
                char c = chars[j];
                if (c != '.') {
                    setSudoku(c-'0',i,j,getBlockIndex(i,j));
                }
            }
        }
    }

    public int getBlockIndex(int row, int col) {
        return (row/3)*3+(col/3);
    }

    public boolean checkSudoku(int num, int row, int col, int block) {
        short i = (short) (1 << num);
        return ((i&rowRecords[row])|
                (i&columnRecords[col])|
                (i&blockRecords[block]))==0;
    }

    public void setSudoku(int num, int row, int col, int block) {
        short i = (short) (1 << num);
        rowRecords[row]|=i;
        columnRecords[col]|=i;
        blockRecords[block]|=i;
    }

    public void deleteSudoku(int num, int row, int col, int block) {
        short i= (short) (~(1 << num));
        rowRecords[row]&=i;
        columnRecords[col]&=i;
        blockRecords[block]&=i;
    }
}
